MacWorld 1999 June/Macworld (1999-06).dmg/Shareware World/Info/For Developers/MacZoop2.0.sea/MacZoop2.0/Required Classes/ZArray.cpp

Text File | 1999-01-27 | 19KB | 728 lines

/*************************************************************************************************
*
*
*            MacZoop - "the framework for the rest of us"
*
*
*
*            ZArray.cpp            -- the basic container class object
*
*
*
*
*
*            © 1996, Graham Cox
*
*
*
*
*************************************************************************************************/


#include    "ZArray.h"
#include    "MacZoop.h"

#include    <stdlib.h>

static short    vCompareFunc( void* a, void* b, const long ref = 0 );


CLASSCONSTRUCTOR( ZArray );

/*-------------------------------***  CONSTRUCTOR  ***----------------------------------*/


ZArray::ZArray( short elementSize )
    : ZComrade()
{
    classID = CLASS_ZArray;

    blkSize = elementSize;
    numElements = 0;
    physicalBlks = kNumPhysicalBlockAlloc;

    FailNIL( a = NewHandle( elementSize * physicalBlks ));
}


/*--------------------------------***  DESTRUCTOR  ***----------------------------------*/

ZArray::~ZArray()
{
    if (a)
        DisposeHandle( a );
}


/*--------------------------------***  INSERTITEM  ***----------------------------------*/
/*
Insert an item at position <index>
----------------------------------------------------------------------------------------*/

void    ZArray::InsertItem(void* item, const long index)
{
    // insert the item into the array at position <index>. The value of <index> is one-based.
    // This extends the array by one item.

    InsertElement( index - 1 );
    SetArrayItem( item, index );

    SendMessage( msgArrayItemInserted, (void*) index );
}


/*--------------------------------***  APPENDITEM  ***----------------------------------*/
/*
add an item at the end of the array
----------------------------------------------------------------------------------------*/

void    ZArray::AppendItem(void* item)
{
    // adds the item to the end of the array. This grows it by one item.

    InsertElement( numElements );
    SetArrayItem( item, numElements );

    SendMessage( msgArrayItemAdded, (void*) numElements );
}


/*-------------------------------***  SETARRAYITEM  ***---------------------------------*/
/*
replace an item at position <index>
----------------------------------------------------------------------------------------*/

void    ZArray::SetArrayItem(void* item, const long index)
{
    // sets the item into the array at <index>, which is one-based.

    ASSERT( "Index out of range; ZArray::SetArrayItem",  index >= 0 && index <= numElements, index )

    BlockMoveData(item, (*a + (blkSize * (index - 1))), blkSize);

    SendMessage( msgArrayItemChanged, (void*) index );
}


/*-------------------------------***  GETARRAYITEM  ***---------------------------------*/
/*
return the item at position <index> (returns a COPY)
----------------------------------------------------------------------------------------*/

void    ZArray::GetArrayItem(void* item, const long index)
{
    // gets the item at poition <index> in the array. Index is one-based.

    ASSERT( "Index out of range; ZArray::GetArrayItem",  index >= 0 && index <= numElements, index )

    BlockMoveData((*a + (blkSize * (index - 1))), item, blkSize);
}


/*---------------------------***  CONCATENATEARRAY  ***---------------------------------*/
/*
appends the array passed to the end of this one. This does not attempt to maintain sort
order, etc- it just joins the arrays. The source array is unaffected and its data is
copied. NOTE: The two arrays *MUST* have the same sized elements- you cannot concatenate
arrays that contain incompatible data types.
----------------------------------------------------------------------------------------*/

void    ZArray::ConcatenateArray( ZArray* anArray )
{
    long    appendedItems;
    long    physExtent;

    FailNILParam( anArray );

    // check element sizes are compatible:

    ASSERT( "Block sizes don't match; ZArray::ConcatentateArray", anArray->blkSize == blkSize, blkSize )

    // is there anything to copy?

    if (( appendedItems = anArray->CountItems()) > 0 )
    {
        // extend our handle to accommodate the additional stuff. Note that since we allocate
        // in multiples of a physical block count, we need to take this into account when
        // joining the arrays

        physExtent = appendedItems + numElements;
        physExtent += kNumPhysicalBlockAlloc - ( physExtent % kNumPhysicalBlockAlloc );

        if ( physExtent > physicalBlks )
        {
            physicalBlks = physExtent;

            SetHandleSize( a, physicalBlks * blkSize );
            FailMemError();
        }

        Ptr p = *anArray->a;
        Ptr    q = *a + ( numElements * blkSize );

        BlockMoveData( p, q, appendedItems * blkSize );

        numElements += appendedItems;
    }
}


/*---------------------------------***  FINDINDEX  ***----------------------------------*/
/*
returns the index of an item in the array, or 0 if not found.
----------------------------------------------------------------------------------------*/

long    ZArray::FindIndex(void* item)
{
    // performs a linear search and returns the index of the item, if found.

    if ( numElements < 1 )
        return 0;

    long        i = 0;
    Boolean        found = FALSE;

    do
    {
        if (EqualMem(*a + ( blkSize * i ), item, blkSize))
        {
            found = TRUE;
            break;
        }
    }
    while( i++ < numElements );

    return ( found? i + 1 : 0 );
}

/*--------------------------------***  DELETEITEM  ***----------------------------------*/
/*
Delete an item at position <index>
----------------------------------------------------------------------------------------*/

void    ZArray::DeleteItem( const long index )
{
    // deletes the item at position <index> (1-based). Items above are moved down one.

    DeleteElement( index - 1 );

    SendMessage( msgArrayItemDeleted, (void*) index );
}


/*---------------------------------***  DELETEALL  ***----------------------------------*/
/*
deletes all items in the array
----------------------------------------------------------------------------------------*/

void    ZArray::DeleteAll()
{
    numElements = 0;
    physicalBlks = kNumPhysicalBlockAlloc;

    SetHandleSize( a, blkSize * physicalBlks );

    SendMessage( msgArrayAllDeleted, NULL );
}


/*----------------------------------***  MOVEITEM  ***----------------------------------*/
/*
move an item from one place in the array to another
----------------------------------------------------------------------------------------*/

void    ZArray::MoveItem( const long curIndex, const long newIndex )
{
    // moves the item at <curIndex> to position <newIndex> (all 1-based), moving other items
    // as needed to keep things in order.

    ASSERT( "Bad index; ZArray::MoveItem", curIndex > 0 && curIndex <= numElements && newIndex > 0 && newIndex <= numElements, 0 )

    void* temp = (void*) NewPtr( blkSize );

    FailNIL(temp);

    // copy the item we want to move to a temporary space

    GetArrayItem( temp, curIndex);

    // delete its current position, which will move stuff as needed

    DeleteElement( curIndex - 1 );

    // insert it into the new position, which moves other stuff as needed

    InsertItem( temp, newIndex );

    // get rid of the temporary space

    DisposePtr((Ptr) temp);
    SendMessage( msgArrayItemMoved, (void*) newIndex );
}


/*----------------------------------***  SWAPITEM  ***----------------------------------*/
/*
Swap two items in the array
----------------------------------------------------------------------------------------*/

void    ZArray::Swap( const long itema, const long itemb )
{
    // swaps items a and b.
    ASSERT( "Bad index; ZArray::Swap", itema > 0 && itema <= numElements && itemb > 0 && itemb <= numElements, 0 )

    // make some swap space

    void* tempa = (void*) NewPtr( blkSize );
    void* tempb = (void*) NewPtr( blkSize );
    FailNIL(tempa);
    FailNIL(tempb);

    GetArrayItem( tempa, itema);
    GetArrayItem( tempb, itemb);
    SetArrayItem( tempa, itemb);
    SetArrayItem( tempb, itema);

    DisposePtr((Ptr) tempa);
    DisposePtr((Ptr) tempb);

    SendMessage( msgArrayItemMoved, (void*) itema );
}


/*---------------------------------***  COUNTITEMS  ***---------------------------------*/
/*
return the number of items in the array
----------------------------------------------------------------------------------------*/

long    ZArray::CountItems()
{
    return numElements;
}


/*----------------------------------***  DOFOREACH  ***---------------------------------*/
/*
for each item in the array, pass it to the grovelling proc passed
----------------------------------------------------------------------------------------*/

void    ZArray::DoForEach(IteratorProcPtr aProc, const long ref)
{
    if (aProc && (numElements > 0))
    {
        long    i = numElements;
        void*    temp = (void*) NewPtr( blkSize );

        FailNIL( temp );

        while ( i )
        {
            GetArrayItem( temp, i);
            (*aProc)(temp, ref);

            // in case the proc changed the item, set it back

            SetArrayItem( temp, i--);
        }

        DisposePtr((Ptr) temp);
    }
}


/*-------------------------------------***  SORT  ***-----------------------------------*/
/*
sort the items in the array into order. The supplied comparison function allows you to
sort anything based on any ordering criteria. Uses a very fast shellsort algorithm. Your
sort function needs to examine the relevant criteria in the items passed, and decide what
order they come in. It should return -1 if a < b, +1 if a > b, and 0 if equal. <ref> can be
anything you want- it is simply passed to the compare function. It might be another object
for example (hint, hint!).

----------------------------------------------------------------------------------------*/

void    ZArray::Sort( register SortCmpProcPtr compareProc, register const long ref )
{
    register long    E,N,M,J,K,R;
    register short    cp;

    register void*    itema;
    register void*    itemb;

    // sanity check- there IS a sort function, right?

    FailOSErr((compareProc == NULL)? kUndefinedCompProcErr : noErr );

    // allocate some temporary storage

    FailNIL(itema = (void*) NewPtr( blkSize ));
    FailNIL(itemb = (void*) NewPtr( blkSize ));

    // initialise the control variables to the number of elements in the list

    M = E = N = numElements;
    N++;

    // and... sort!

    do
    {
        M /= 2;
        if (M <= 0)
            break;

        K = E - M;
        J = 1;

        do
        {
            N = J;
            do
            {
                R = N + M;
                GetArrayItem( itema, N );                        // get first item
                GetArrayItem( itemb, R );                        // get second item

                cp = (*compareProc)( itema, itemb, ref );        // call the comparison function

                if ( cp < 1 )                                    // no need to swap (a <= b)
                    break;

                Swap( N, R );                                    // swap items in the array

                N -= M;
            }
            while ( N > 0 );
            J++;
        }
        while (J <= K);
    }
    while( M > 0 );

    // all done, now release the temporary storage

    DisposePtr((Ptr) itema);
    DisposePtr((Ptr) itemb);
}

/*-------------------------------------***  SORT  ***-----------------------------------*/
/*
simpler interface to Sort- indirectly calls the Compare method, which you can override.

----------------------------------------------------------------------------------------*/

void    ZArray::Sort()
{
    Sort( vCompareFunc, (long) this );
}

/*------------------------------------***  QSORT  ***-----------------------------------*/
/*
sorts using qsort in std C lib, which can take from 1/4 to 1/2 the time as Sort. Note
though that you cannot pass a <ref>, so you compare proc must NOT rely on it for any
purpose if using QSort instead of Sort.
----------------------------------------------------------------------------------------*/

void    ZArray::QSort( SortCmpProcPtr compareProc )
{
    char    hs = HGetState( a );

    HLock( a );

    qsort( *a, numElements, blkSize, ( int(*)( const void*, const void* )) compareProc );

    HSetState( a, hs );
}

/*----------------------------------***  COMPARE  ***-----------------------------------*/
/*
compare two items and return their relative ordering: -1 if a < b, +1 if a > b, 0 if a == b.
You need to override this if you wish to use the simple call to Sort() above.
----------------------------------------------------------------------------------------*/

short    ZArray::Compare( void* itema, void* itemb, const long ref )
{
    return 0;
}

/*------------------------------***  INSERTSORTEDITEM  ***------------------------------*/
/*
insert the item into the list at the correct place assuming the list is sorted. This
does a binary search to locate the position, based on the comparison function provided.
Normally the comparison function is the same one you'd use with sort, so everything
agrees. Returns the index position it was inserted at.
----------------------------------------------------------------------------------------*/

long    ZArray::InsertSortedItem( void* item, SortCmpProcPtr compareProc, const long ref )
{
    FailNILParam( compareProc );

    short    rel;
    long    pos = BFindIndex( item, compareProc, ref );
    void*    itemB;

    // <pos> represents the NEAREST item, but we don't know if we need to insert
    // before or after this item, so we need to do one more compare

    if ( pos > 0 )
    {
        FailNIL( itemB = (void*) NewPtr( blkSize ));

        GetArrayItem( itemB, pos );

        rel = (*compareProc)( item, itemB, ref );

        DisposePtr((Ptr) itemB );

        if ( rel > 0 )
            pos++;
    }

    if (( pos > numElements ) || ( pos == 0 ))
    {
        AppendItem( item );
        pos = numElements;
    }
    else
        InsertItem( item, pos );

    return pos;
}

/*------------------------------***  INSERTSORTEDITEM  ***------------------------------*/
/*
insert the item into the list at the correct place assuming the list is sorted. This uses
the built in compare function which calls the Compare method.
----------------------------------------------------------------------------------------*/

long    ZArray::InsertSortedItem( void* item, const long ref )
{
    return InsertSortedItem( item, vCompareFunc, ref );
}


/*-----------------------------***  Protected Members  ***------------------------------*/


/*-------------------------------***  INSERTELEMENT  ***--------------------------------*/
/*
make space for one element in the handle
----------------------------------------------------------------------------------------*/

void    ZArray::InsertElement( const long index )
{
    // grow the handle by one element, moving items above <index> up one. This also
    // sets the numElements data member. Index is zero-based.

    long    newSize;

    // check that the index parameter is sensible

    ASSERT( "Index out of range; ZArray::InsertElement",  index >= 0 && index <= numElements, index )

    // grow the handle if the number of physical blocks is insufficient

    newSize = ( numElements + 1 ) * blkSize;

    if ( newSize > ( physicalBlks * blkSize ))
    {
        physicalBlks += kNumPhysicalBlockAlloc;

        SetHandleSize( a, physicalBlks * blkSize );
        FailOSErr(MemError());
    }

    // OK, the handle is now larger by one element- do we need to move any data around?

    if (index < numElements)
    {
        // yes, subsequent entries move up by <blkSize> bytes

        HLock( a );
        BlockMoveData(    *a + (blkSize * index),
                        *a + (blkSize * (index + 1)),
                        blkSize * (numElements - index));
        HUnlock( a );
    }

    // increment the count of elements

    numElements++;
}

/*-------------------------------***  DELETEELEMENT  ***--------------------------------*/
/*
remove space for one element in the handle
----------------------------------------------------------------------------------------*/

void    ZArray::DeleteElement( const long index )
{
    // shrink the handle by one element, after moving entries above <index> down by one.
    // <index> is zero-based.

    // check that the index parameter is sensible

    ASSERT( "Index out of range; ZArray::DeleteElement",  index >= 0 && index < numElements, index )

    // one less element

    numElements--;

    // if the index is not the last item, move everything down to fill the space

    if (index < numElements)
    {
        HLock( a );
        BlockMoveData(    *a + (blkSize * (index + 1)),
                        *a + (blkSize * index),
                        blkSize * (numElements - index + 1));
        HUnlock( a );
    }

    // shrink the handle if we can remove a whole multiple of physical blocks

    if (( physicalBlks - numElements ) > kNumPhysicalBlockAlloc )
    {
        physicalBlks = MAX( 0, physicalBlks - kNumPhysicalBlockAlloc );
        SetHandleSize( a, blkSize * physicalBlks );
    }
}


/*---------------------------------***  BFINDINDEX  ***---------------------------------*/
/*
use the compare function to determine where the item SHOULD be inserted (binary search)
----------------------------------------------------------------------------------------*/

long    ZArray::BFindIndex( void* item, SortCmpProcPtr compareProc, const long ref )
{
    unsigned long    lowItem, highItem, midItem, pos = 1;
    short            compare;
    void*            itemB;

    FailNILParam( compareProc );

    lowItem = 1;
    highItem = numElements;

    // if the list is empty, we return item 1, since we can simply append the item.

    if ( numElements < 1 )
        pos = 0;
    else
    {
        // make space for the item we are going to compare

        FailNIL( itemB = (void*) NewPtr( blkSize ));

        while ( lowItem <= highItem )
        {
            midItem = ( highItem + lowItem ) >> 1;

            GetArrayItem( itemB, midItem );

            // compare this item to the one we are looking for

            compare = (*compareProc)( item, itemB, ref );

            // if an exact match, then insert right here

            if ( compare == 0 )
                break;

            // otherwise search half the list

            if ( compare > 0 )
                lowItem = midItem + 1;
            else
                highItem = midItem - 1;
        }

        DisposePtr((Ptr) itemB );
        pos = MAX( midItem, 1 );
    }

    return pos;
}


/*------------------------------***  READFROMSTREAM  ***--------------------------------*/
/*
rebuild/initialise array from stream. This overwrites/removes any existing contents.
----------------------------------------------------------------------------------------*/

void    ZArray::ReadFromStream( ZStream* aStream )
{
#if _MACZOOP_STREAMS
    ZComrade::ReadFromStream( aStream );

    // read array data items from the stream. First item is block size, then count.

    aStream->ReadLong( &blkSize );
    aStream->ReadLong( &numElements );

    // if num elements is not 0, read data into array's storage handle

    if ( numElements > 0 )
    {
        if ( a )
            DisposeHandle( a );

        aStream->ReadHandle( &a );

        // the number of phyical blocks needs to be adjusted to this size.
        // We do not bother rounding this up to a whole multiple of
        // the physical block count- it'll work anyway.

        physicalBlks = GetHandleSize( a ) / blkSize;
    }
#endif
}


/*-------------------------------***  WRITETOSTREAM  ***--------------------------------*/
/*
write entire array object to stream
----------------------------------------------------------------------------------------*/

void    ZArray::WriteToStream( ZStream* aStream )
{
#if _MACZOOP_STREAMS
    ZComrade::WriteToStream( aStream );

    // write all the array items to the stream.

    long    i, numItems;
    void*    temp;

    numItems = CountItems();

    // first two items in stream are block size and item count

    aStream->WriteLong( blkSize );
    aStream->WriteLong( numItems );

    // ...followed by the data:

    if ( numItems > 0 )
        aStream->WriteHandle( a );
#endif
}



#pragma mark -
/*--------------------------------***  vCompareFunc  ***--------------------------------*/

static short    vCompareFunc( void* a, void* b, const long ref)
{
    ZArray*        theArray = (ZArray*) ref;

    if ( theArray )
        return theArray->Compare( a, b, ref );
    else
        return 0;
}